#include <iostream>
#include <vector>

using namespace std;

const int N = 1e4 + 10, INF = 2147483647; 

typedef pair<int, int> PII;

int n, m, s;
vector<PII> edges[N];

int dist[N];
bool st[N];

void dijkstra(int s)
{
	for(int i = 0; i <= n; i++) dist[i] = INF;
	dist[s] = 0;
	for(int i = 1; i < n; i++)
	{
		int a = 0;
		for(int j = 1; j <= n; j++)
			if(!st[j] && dist[j] < dist[a])
				a = j;
				
		st[a] = true;
		
		for(auto x : edges[a])
		{
			int b = x.first, c = x.second;
			if(!st[b] && dist[a] + c < dist[b])
				dist[b] = dist[a] + c;
		}
	}
	for(int i = 1; i <= n; i++) cout << dist[i] << " ";
}

int main()
{
	cin >> n >> m >> s;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		edges[u].push_back({v, w});
	}
	
	dijkstra(s);
	
	return 0;
}
